#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/5 18:04
# @USER    : Shengji He
# @File    : MergeTwoSortedLists.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        """
        Merge two sorted linked lists and return it as a new sorted list.
        The new list should be made by splicing together the nodes of the first two lists.

        Example:
            Input: 1->2->4, 1->3->4

            Output: 1->1->2->3->4->4

        :param l1: ListNode
        :param l2: ListNode
        :return: ListNode
        """
        output = ListNode(0)
        node = output
        while l1 or l2:
            if l1 is None and l2 is not None:
                node.next = l2
                break
            elif l1 is not None and l2 is None:
                node.next = l1
                break
            else:
                if l1.val > l2.val:
                    node.next = ListNode(l2.val)
                    l2 = l2.next
                else:
                    node.next = ListNode(l1.val)
                    l1 = l1.next
                node = node.next

        return output.next


if __name__ == '__main__':
    S = Solution()
    input1 = [1, 2, 4]
    input2 = [1, 3, 4]
    print(input1)
    print(input2)
    l1 = ListNode(input1.pop(0))
    l2 = ListNode(input2.pop(0))
    temp1 = l1
    for element in input1:
        temp1.next = ListNode(element)
        temp1 = temp1.next
    temp2 = l2
    for element in input2:
        temp2.next = ListNode(element)
        temp2 = temp2.next
    output = S.mergeTwoLists(l1, l2)
    print('done')
